When digital-data-modulated signals are to be transmitted over a rapidly fading communication channel, such as a skywave radio channel or a mobile radio telephone system, a technique sometimes used to cope with the changing channel is to include a predetermined data symbol pattern in the transmitted signal at suitably frequent intervals. The known symbol pattern is used in a receiver by a channel equalizer to adapt a demodulator to the channel's characteristics. This procedure is known as "training" the equalizer (which is then sometimes referred to as a preset equalizer), and the predetermined symbol pattern is then known as the "training" pattern. The training procedure may also involve correlating the received signal with one or more shifts of the training pattern to determine a corresponding number of points (phase and amplitude) of the channel's impulse response.
The equalizer typically used implements a linear, finite-impulse-response ("FIR") model of the channel, that is a transversal filter or a tapped delay line having complex multiplication weights applied to the tap outputs. The weighted outputs are summed to predict, for each possible data symbol pattern that can be contained within the time span of the channel's impulse response, the signal waveform that should be received for the next data symbol. The predicted waveforms are compared with the actually received waveform, and "votes" for and against the probability of each data symbol pattern being "correct" (i.e., the pattern received) are accumulated. Each "vote" is based on the accuracy of the match between a predicted waveform and the received waveform. The data symbol patterns that can be contained within the time span of the channel's impulse response correspond to the "states" of the system. Such equalizers are described in F. Stremler, Introduction to Communication Systems, pp. 544-551, Addison-Wesley Publishing Co., Inc. (1982) and are also known as "Viterbi" equalizers.
The weights applied to the delay line tap outputs are the coefficients, c.sub.1, c.sub.2, c.sub.3, . . . , in the equation: EQU S.sub.i=c.sub.l D.sub.i +c.sub.2 D.sub.i-l +c.sub.3 D.sub.i-2 +. . .
where S.sub.i is the predicted signal for the sequence of data symbol patterns D.sub.i, D.sub.i-l, D.sub.i-2, . . . . The coefficients are usually calculated from the known training pattern. In the case of signalling by binary data symbols (i.e., 1 and 0), the number of predicted signals that must be calculated is 2.sup.n, where n-1 is the number of bits in each data symbol pattern D. It will be understood that ternary and quaternary data symbols can also be used.
Methods for optimally updating the channel model from the received signal, such as that described in European Patent Application No. 90850301.4, filed Sep. 10, 1990, are also known, and the best methods maintain a separate channel model for each Viterbi state. When one of the states is selected as the best predecessor of a new state, the channel model corresponding to that state is updated and becomes the channel model for the new state. In this way, it is ensured that the channel models are always derived from the best demodulated data sequences received up to that time.
U.S. patent application Ser. No. 07/894,933, filed Jun. 8, 1992, for "Adaptive Maximum Likelihood Modulator" describes a variation of the adaptive Viterbi equalizer that does not employ channel models to generate the predictions except during system start-up, and thus does not update the channel model parameters. Instead, direct updating of the signal predictions for each state, without going through the intermediate step of first updating the channel models, is described. U.S. patent application Ser. No. 07/894,933 is hereby incorporated by reference into the present application.
The known Viterbi equalizer incorporates the following steps: (1) determining the tap coefficients for a Finite Impulse Response (FIR) model of the channel; (2) for all possible data symbol sequences that can be postulated to be contained within the impulse response length of the channel model, predicting the signal value that should be received based on the determined tap coefficients; (3) comparing each postulated value with the actually received signal value and calculating the mismatch (usually by squaring the difference between the received and postulated values); (4) for each postulated symbol sequence, adding the calculated mismatch to the cumulative mismatch of predecessor sequences that are consistent with the postulated symbol sequence, also called "the state" (the cumulative mismatch values are called "path metrics"); and (5) choosing the "best" of the possible predecessor sequences that can transition to the new postulated state, i.e., choosing the predecessor sequence that gives the lowest path metric for the new state. Thus, the path metrics can be considered confidence factors that represent the degrees of correlation between the postulated symbol sequences and the actually received signal.
It will be appreciated that the Viterbi equalizer is a form of sequential maximum likelihood sequence ("SMLS") estimator that decodes, or demodulates, the received data symbol stream. SMLS estimators and other decoding methods are described in Clark and Cain, Error-Correction Coding for Digital Communications, Plenum Press (1981).
FIG. 2 illustrates the data structure and flow within a Viterbi equalizer having 16 states, the predicted signal values being assumed to depend on four previous binary symbols (bits) plus one new bit. The channel impulse response length for this example is thus five symbols, i.e. the latest echo can be four symbols delayed compared to the shortest signal path.
Referring to FIG. 1, a Viterbi processing cycle begins by assuming the postulated symbol history of state 0000 to be true, and that a new bit `0` was transmitted. Consequently, using the channel model (40), the signal value that should be observed given the 5-bit symbol history 00000 is predicted. This is compared in comparator (50) with the actual received signal value and a mismatch value produced. This is added in adder (51) with the previous state 0000 path metric to produce a candidate metric for a new 0000 state.
However, another candidate for the new path metric of new state 0000 can be derived by assuming state 1000 to contain the true history, with a new bit of `0`. This is because both 0000-0 and 1000-0 lead to new state 1-0000 (0-0000) when the oldest (left-most) bit is left shifted out of the 4-bit state number and into the symbol history memory. This candidate is evaluated by applying 10000 to the channel model (40), comparing the prediction so-obtained with the input signal value in comparator (50) and adding the resultant mismatch with the previous cumulative mismatch (path metric) associated with state 1000 in adder (52). The two candidate values from adders 51 and 52 are then compared in a comparator 53, and the lower of the two is selected to become the new path metric of new state 0000. Furthermore, the contents of the history memory (55) associated with the selected predecessor state is selected to be the symbol history of the new state 0000. Also, the selected bit history is left-shifted and a 0 or 1 entered in the right-most position according as state 0000 or 1000 gave rise to the selected candidate path metric.
The above procedure is then repeated with the assumption that the new bit is a `1` in order to produce a new state 0001, also with either state 0000 or 1000 as candidate predecessors.
The above procedure is then repeated using every pair of states, which are 8 states apart, to derive all 16 new states, as follows:
0001,1001 to produce new states 0010 and 0011 PA1 0010,1010 to produce new states 0100 and 0101 PA1 0011,1011 to produce new states 0110 and 0111 PA1 0100,1100 to produce new states 1000 and 1001 PA1 0101,1101 to produce new states 1010 and 1011 PA1 0110,1110 to produce new states 1100 and 1101 PA1 0111,1111 to produce new states 1110 and 1111
At the end of the above processing cycle, one signal sample has been processed and one extra bit has been demodulated and inserted into symbol history memories (55). There is a tendency for the older bits in the history memories to converge to the same value, at which point that bit can be extracted as a final unambiguous decision and the history memory shortened 1 bit. Other methods of truncating history memory growth are known to the art, such as taking the oldest bit from the state having the lowest path metric.
It will be understood that the Viterbi equalizer recognizes that some sequences of data symbol patterns, and thus some sequences of predicted waveforms, are not valid. For example, a prediction that the channel carried the binary data symbol pattern 10010 at one instant (i.e., one bit period) and a prediction that the channel carried the binary data symbol pattern 11001 at the next instant (i.e., the next bit period) are inconsistent because the pattern 10010 can be followed only by the patterns 00100 or 00101 (assuming a left-shift in passing through the channel.) Also under such conditions, each of the 00100 and 00101 patterns can have only either 10010 or 00010 as predecessors. Thus, a set of transition rules constrains the number of ways the votes can be sequentially accumulated for each sequence of predicted waveforms.
It will be appreciated that such prior demodulators operate on the received signal only in the forward direction: a received training pattern is used to develop predicted waveforms for yet-to-be-received data symbols. If the training pattern is lost or excessively distorted due to severe channel fading, intersymbol interference, frequency errors, etc., such forward demodulators must wait until the next training pattern is successfully received before they are able to demodulate accurately. As a result, data sent in the intervening periods between training patterns can be lost.